% Helper function to determine if G* is Hamiltonian
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function isHamiltonianFlag = isHamiltonian(Gstar,varargin)
%  
%   This function will print out an output for if the graph Gstar is
%   Hamiltonian through a fairly trivial algorithm. This will probably wind
%   up being used as another helper function.
%
%   INPUTS:     Gstar - graph created from G after removing all pendant
%                       vertices (made from GtoGstar())
%   OUTPUTS:    isHamiltonianFlag - is 1 if graph is Hamiltonian, else 0            
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function isHamiltonianFlag = isHamiltonian(Gstar,varargin)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% So the idea here is actually fairly different. The goal of how to find a
% Hamiltonian circuit is to traverse through every vertex and then return
% to the start.  Price had a brute force algorithm suggestion of this
% nature:
%
%   1. Start at one vertex (let's say one)
%   2. Choose one of the vertices and traverse until it doesn't result in a
%      Hamiltonian cycle
%   3. Turn back to the point where it no longer worked and try another
%      path
%   4. When all paths fail on a given vertex, return back to the previous
%      vertex
%   5. If all possible paths have been exhausted with no success, the graph
%      is not hamiltonian.
%
% This needs to be made more efficient.  I don't know what the run time is
% but it needs to reduce greatly.  I have to think of a way to quickly do
% this.  One possibility is make a small 2d matrix of number of elements by
% 10, since I think the max degree of each vertex is less than 10.  That
% way each for loop only goes up to 10 instead of 46.  That may shave down
% on the amount of time, but it's probably still a pretty large gamble and
% may not work like I hope.  I'll have to jot some notes on this code.
%
% The biconnected check is implemented.  Still takes about 40-50 minutes to
% finish finding a hamiltonian cycle on a school computer.  Maple does it
% in about 20.  
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% note - this assumes the graph is already in G* form

% A few initializations
isHamiltonianFlag = 0;
[xmax ymax]=size(Gstar);

% First test is to see if removing a vertex from the graph will cause leaf
% nodes or disconnected nodes.  Remove vertex and check to see if there are
% more than 2 vertices of degree 1.  If this happens, graph is not
% biconnected and therefore not hamiltonian.  We'll test by removing each
% vertex and counting the degrees of all vertices
disconnected = 0;
for y = 1:ymax
    gtest = removeVertex(y,Gstar);
    if (disconnected == 0)
        disconnected = 0;
        s = sum(gtest);
        for x = 1:(xmax-1)
            if (s(x) == 1),
                disconnected = disconnected + 1;
            end;
        end;

        % Check to see how many pendant vertices exist.  If there are more than 2,
        % graph is disconnected
        if (disconnected > 2),
            sprintf('G* is not Hamiltonian since it is not biconnected')
            disconnected = 1;
        else
            disconnected = 0;
        end;
    end;
end;

tic
% Make the necessary variables for functionality
visitedArray = zeros(xmax,1);
currentNode = 1;
visitedArray(1) = 1; 

% First we check to see if all of them are visited.
if (sum(visitedArray) == xmax),
    isHamiltonianFlag = 1;
 
% If the graph passed the biconnected test, we will need to brute force 
% search for a Hamiltonian cycle
elseif(disconnected == 0),    
    % Now we need to loop through all of the indexes 
    for x = 1:xmax
        % if the edge exists but we haven't visited the node
        if (Gstar(currentNode,x) == 1 && visitedArray(x) == 0)
            isHamiltonianFlag = isHamiltonianHelper(Gstar,visitedArray,x,xmax,ymax);
        end;
    end;
end;

if (isHamiltonianFlag == 1),
    sprintf('G* is Hamiltonian by brute force search')
else
    sprintf('G* is not Hamiltonian by brute force search')
end;